// 331.验证二叉树的前序序列化

package Leetcode;

public class Solution331 {
    public boolean isValidSerialization(String preorder) {
        String[] split = preorder.split(",");
        int diff = 1; // 根节点的出度-入度=2，这里设置为1作为补偿
        for (String node : split) {
            // 每个节点都有一个入度
            diff--;
            // 如果消耗完一个入度之后，diff小于0，表示出度数量在此时小于入度，返回false
            // 例子：#,#,3,5,#
            if (diff < 0)
                return false;
            // 如果是非叶子节点，提供两个出度
            if (!"#".equals(node))
                diff += 2;
        }
        return diff == 0;
    }
}
